package org.JavaAlgorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Solution {
    private ArrayList<String> allList = new ArrayList<String>();
    public static void main(String[] args) {
		String s = "catsanddog";
		Set<String> dict= new HashSet<String>();
		dict.add("cat");
		dict.add("cats");
		dict.add("sand");
		dict.add("dog");
		dict.add("and");
		ArrayList<String> allList = wordBreak(s,dict);
		Collections.reverse(allList);
		System.out.println(allList.toString());
	}
    public static ArrayList<String> wordBreak(String s, Set<String> dict) {
    	Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        return dfs(s,dict,map);
    }
    
    public  static ArrayList<String> dfs(String s, Set<String> dict, Map<String, ArrayList<String>> map) {
        if (map.containsKey(s))
            return (ArrayList<String>) map.get(s);
         
        ArrayList<String> lists = new ArrayList();
        if (s.equals("")){
        	lists.add("");
        }else {
            int len = s.length();
            for (int i = 1; i <= len; i++) {
                String sub = s.substring(0, i);
                if (dict.contains(sub)) {
                    ArrayList t = dfs(s.substring(i, len), dict, map);
                    if (t.size() == 0) {
                        //lists.add(sub);
                    	continue;
                    } else {
                        for (int j = 0; j < t.size(); j++) {
                            StringBuilder sb = new StringBuilder();
                            sb.append(sub).append(" ").append(t.get(j));
                            lists.add(sb.toString().trim());
 
                        }
                    }
                }
            }
        }
        map.put(s, lists);
        return lists;
    }
    
}